[54, 226, 93, 17, 77, 31, 44, 55, 20]  #升序排序

[54,      226, 93, 17, 77, 31, 44, 55, 20]
[54, 93,226,       17, 77, 31, 44, 55, 20]
[54, 93,17,226,        77, 31, 44, 55, 20]
[54,17, 93,226,        77, 31, 44, 55, 20]
[17,54, 93,226,        77, 31, 44, 55, 20]
[17,54, 93,77,226,         31, 44, 55, 20]
[17,54,77, 93,226,         31, 44, 55, 20]

# .....
[17,31, 44,54,55,77,93,226,   15]
#最坏时间复杂度  n*n=O(n^2)
#最优时间复杂度  n*1=O(n)
[17, 20, 31, 44, 54, 55, 77, 93, 226,  1000]

#稳定性 :稳定的
[17, 20, 31, 44, 54, 55, 77, 93,   77, 226]
[17, 20, 31, 44, 54, 55, 77, 77,   93, 226]

#插入排序
def insert_sort(alist):
    n=len(alist)
    for j in range(1,n):  #n-1   n
        i=j
        while i>0: #和有序列表中每个元素进行比较 （从最后一个开始）
            if alist[i]<alist[i-1]: #如果当前元素比前一个元素小，则进行交换
                alist[i],alist[i-1],=alist[i-1],alist[i]
            else:#否则已经是有序列表，不需要交换了，则退出循环
                break
            i-=1

if __name__ == '__main__':
    alist=[54, 226, 93, 17, 77, 31, 44, 55, 20]
    print('原数组：')
    print(alist)
    print('排序后：')
    insert_sort(alist)
    print(alist)